package fag.core.collision;

import java.util.ArrayList;
import java.util.List;

import fag.core.geometry.Vector2D;

/**
 * Classe de l'algorithme Gilbert–Johnson–Keerthi. Utilisé pour la détection de collisions.
 * @author lumz
 */
public class Gjk {
	
	/**
	 * Résultat de l'algorithme Gjk.
	 * @author lumz
	 */
	public static class Result {
		
		private boolean isColliding = false;
		private List<Vector2D> simplex = new ArrayList<Vector2D>();
		
		/**
		 * Constructeur par défault.
		 */
		private Result(boolean isColliding, List<Vector2D> simplex) {
			this.isColliding = isColliding;
			this.simplex = simplex;
		}
		
		/**
		 * Accesseur de la valeur de vérité de la collision.
		 * @return Vrai si les deux objets sont en collision, sinon faux.
		 */
		public boolean isColliding() {
			return isColliding;
		}
		
		/**
		 * Accesseur du simplex final. Le simplex retourné est toujours
		 * un 2-simplex, format nécessaire pour l'exécution d'Epa.
		 * @return Le simplex final.
		 */
		public List<Vector2D> getSimplex() {
			
			assert(isColliding);
			
			List<Vector2D> simplexClone = new ArrayList<Vector2D>();
			simplexClone.addAll(simplex);
			
			return simplexClone;
		}
		
	}
	
	private final static int MAX_LOOPS = 100;
	
	/**
	 * Constructeur par défaut de Gjk.
	 */
	private Gjk() {
	}

	/**
	 * Obtenir le résultat de l'algorithme.
	 * @param c1 Premier objet SupportMapping.
	 * @param c2 Deuxième objet SupportMapping.
	 * @return Le résultat de l'algorithme Gjk.
	 */
	public static Result getResult(Hitbox c1, Hitbox c2) {
		
		List<Vector2D> simplex = new ArrayList<Vector2D>();
		simplex.add(minkowskiSupportMapping(c1, c2, new Vector2D(1, 0)));
		Vector2D a, d;
		
		int loops = 0;
		while(loops++ < MAX_LOOPS)
		{
			d = computeSupportDirection(simplex);
			a = minkowskiSupportMapping(c1, c2, d);
		
			// Si A se rapproche de l'origine alors l'ajouter au simplex,
			// sinon aucune collision.
			if(a.dot(d) < 0)
				return new Result(false, null);
			
			simplex.add(a);
			
			// Si la mise à jour échoue alors le simplex contient déjà l'origine, d est le vecteur de collision.
			if(!updateSimplex(simplex, d)) {
				return new Result(true, simplex);
			}
		}
		
		return new Result(false, null);
	}
	
	/**
	 * Calculer le vecteur d'assistance. Le plus court vecteur du simplex à l'origine.
	 * @return Le vecteur d'assistance.
	 */
	private static Vector2D computeSupportDirection(List<Vector2D> simplex) {

		int size = simplex.size();
		assert(size > 0 && size < 3);
		
		Vector2D a = simplex.get(size -1);
		
		switch(size) {
		case 1:
			return a.mul(-1);
		
		case 2:
			Vector2D b = simplex.get(size -2);
			
			double ll = Math.pow(b.x - a.x, 2) + Math.pow(b.y - a.y, 2);
			double r = (a.y * (a.y - b.y) - (a.x * (b.x - a.x))) / ll;
			
			return new Vector2D(a.x + r * (b.x - a.x), a.y + r * (b.y - a.y)).mul(-1);
		
		default:
			return null;
		}
	}
	
	/**
	 * Calcule le point dans la différence de Minkowski le point dont la projection est la plus éloignée le long de d.
	 */
	private static Vector2D minkowskiSupportMapping(Hitbox c1, Hitbox c2, Vector2D d) {
		return c1.supportMapping(d).sub(c2.supportMapping(d.mul(-1)));
	}
	
	/**
	 * Tenter de réduire la taille du simplex.
	 */
	private static boolean updateSimplex(List<Vector2D> simplex, Vector2D d) {
		
		int size = simplex.size();
		Vector2D a = simplex.get(size -1);
		Vector2D b = simplex.get(size - 2);
		Vector2D ab = b.sub(a);
		
		switch(size) {
		case 2: // 1-simplex

			// Il faut encore se rapprocher de l'origine
			if(a.dot(d) < 0)
				simplex.remove(b);
			
			break;

		case 3: // 2-simplex
			
			Vector2D c = simplex.get(size - 3);
			Vector2D ao = a.mul(-1);
			Vector2D ac = c.sub(a);
			
			// Si l'origine est à droite de AC
			if(ao.det(ac) > 0) {
				// Si l'origine est devant A
			    if(ao.dot(ac) > 0) {
			        simplex.remove(b);
			    }
			    // Si l'origine est derrière A
			    else {
			        simplex.remove(b);
			        simplex.remove(c);
			    }
			}
			// Si l'origine est à gauche de AB
	        else if(ao.det(ab) < 0) {
	        	// Si l'origine est devant le point A sur AB
			    if(ab.dot(ao) > 0) { 							
			        simplex.remove(c);
			    }
			    // Si l'origine est derrière A sur AB
			    else { 											
			    	simplex.remove(b);
			        simplex.remove(c);
			    }
	        }
			// L'origine est à la droite de AC et à la gauche de AB, il y a intersection.
			else {
			    return false;
			}
		}
		
		return true;
	}
}